package com.my.algorithmlearning.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName Medium_207_CourseSchedule
 * @Description 优秀题解：https://leetcode.cn/problems/course-schedule/solutions/250377/bao-mu-shi-ti-jie-shou-ba-shou-da-tong-tuo-bu-pai-/
 * @Author wanghaiwei
 * @Date 2023/6/14 14:34
 */
public class Medium_207_CourseSchedule {
    public static void main(String[] args) {
        Medium_207_CourseSchedule courseSchedule = new Medium_207_CourseSchedule();
        System.out.println(courseSchedule.canFinish(2, new int[][]{{1, 0}}));
        System.out.println(courseSchedule.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
        System.out.println(courseSchedule.canFinish(3, new int[][]{{1, 0}, {1, 2}, {0, 1}}));
        System.out.println(courseSchedule.canFinish(4, new int[][]{{2, 0}, {1, 0}, {3, 1}, {3, 2}, {1, 3}}));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //定义一个数组用来标记第i个课程的访问情况，0表示未访问，1表示已访问，-1表示访问过且从此节点开始没有环
        int[] visited = new int[numCourses];
        //使用HashMap来存储课程的依赖关系，key为课程，value为依赖的课程
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            if (map.containsKey(prerequisite[0])) {
                map.get(prerequisite[0]).add(prerequisite[1]);
            } else {
                List<Integer> values = new ArrayList<>();
                values.add(prerequisite[1]);
                map.put(prerequisite[0], values);
            }
        }
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == -1) {
                continue;
            }
            boolean canLearn = dfsCanLearn(i, visited, map);
            if (!canLearn) {
                return false;
            }
            visited[i] = 0;
        }
        return true;
    }

    private boolean dfsCanLearn(int currCourse, int[] visited, Map<Integer, List<Integer>> map) {
        List<Integer> preCourses = map.get(currCourse);
        if (preCourses == null) {
            visited[currCourse] = -1;
            return true;
        }
        if (visited[currCourse] == 1) {
            return false;
        }
        if (visited[currCourse] == -1) {
            return true;
        }
        visited[currCourse] = 1;
        for (Integer preCourse : preCourses) {
            boolean preCourseCanBeLearn = dfsCanLearn(preCourse, visited, map);
            if (preCourseCanBeLearn) {
                visited[preCourse] = -1;
            } else {
                return false;
            }
        }
        return true;
    }
}
